package jianzhi_offer;

public class _50_构建乘积数组 {
    public static void main(String[] args) {
        _50_构建乘积数组 test = new _50_构建乘积数组();
        test.multiply(new int[]{1,2,3,4});
    }
    //不能用除法
    public int[] multiply(int[] A) {
        if(A == null || A.length == 0) return new int[0];
        int []left= new int[A.length+2];
        int []right = new int[A.length+2];
        left[0] = 1;
        left[left.length-1] =1;
        right[0] = 1;
        right[right.length-1] =1;

        for(int i=0;i<A.length;++i){
            left[i+1] = A[i]*left[i];
        }
        for(int i=A.length;i>0;--i){
            right[i] = right[i+1]*A[i-1];
        }
        for(int i=0;i<A.length;++i){
            A[i] = left[i]*right[i+2];
        }
        return A;
    }
}
